struct Node
{
    int key;
    Node* next;
    Node(int nKey, Node* pNext)
        :key(nKey)
        ,next(pnext)
    {}
};

Node * GetPartion(Node* pBegin, Node* pEnd)
{
    int key = pBegin->key;
    Node* p = pBegin;
    Node* q = p->next;

    while(q!=pEnd)
    {
            if(q->key < key)
            {
                p = p->next;
                swap(p->next, q->key);
            }

            q = q->next;
    }
    swap(p->key, pBegin->key);
    return p;
}

void QuickSort(Node *pBegin, Node* pEnd)
{
    if(pBegin != pEnd)
    {
        Node* partion = GetPartion(pBegin, pEnd);
        QuickSort(pBegin, partion);
        QuickSort(partion->next, pEnd);
    }
}